package chapter03_binaryTree.lowestAncestor;

import chapter03_binaryTree.Node;

import java.util.HashMap;

/**
 * 描述：
 *      并查集（哈希表实现）,关于二叉树
 * @author hl
 * @date 2021/5/31 16:38
 */
public class DisjiontSets {
    //表示当前结点所属集合的代表结点，初始时father指向自身
    HashMap<Node, Node> fatherMap;
    //表示当前结点下面有多少层，初始时为0
    //除了每个集合的代表结点，其他结点的rank是没有意义的，因为在findFather过程中，非代表结点的rank都会变为0
    HashMap<Node, Integer> rankMap;

    public DisjiontSets() {
        fatherMap = new HashMap<>();
        rankMap = new HashMap<>();
    }

    /**
     * 对二叉树结构并查集初始化
     * @param head
     */
    public void makeSets(Node head){
        fatherMap.clear();
        rankMap.clear();
        preOrderMaker(head);
    }
    public void preOrderMaker(Node head){
        if (head == null) {
            return ;
        }
        fatherMap.put(head, head);
        rankMap.put(head, 0);
        preOrderMaker(head.left);
        preOrderMaker(head.right);
    }

    /**
     * 查找并返回当前结点所在集合的代表结点，并且在查找的过程中将查找的路径压缩，让路径上的每个结点的father直接指向当前集合的代表结点
     * @return
     */
    public Node findFather(Node n){
        Node father = fatherMap.get(n);
        while(father != n){
            father = findFather(father);
        }
        fatherMap.put(n, father);
        return father;
    }

    public void union(Node a, Node b){
        Node aF = findFather(a);
        Node bF = findFather(b);
        if (aF != bF) {
            int al = rankMap.get(aF);
            int bl = rankMap.get(bF);
            //将层级小的挂在层级大的下面，层级大的rank不用改变
            if (al > bl) {
                fatherMap.put(bF, aF);
            }else if (al < bl) {
                fatherMap.put(aF, bF);
            }else{
                fatherMap.put(bF, aF);
                rankMap.put(aF, al + 1);
            }
        }
    }
}
